package util;

import struct.tree.node.Node;

import java.util.*;

/**
 * @author: 柒月
 * @date: 2025/5/2 下午10:47
 * @version: 1.0
 */
public class TreeUtil {

    /**
     * @param size  二叉树节点的个数
     * @param range 二叉树节点的大小 [1,range)
     * @return 返回一个普通的二叉树
     */
    public static Node getRandTree(int size, int range) {
        int[] arrays = ArrayUtil.randArrays(size, range);
        Node root = arrayToRandTree(arrays);
//        System.out.println("生成的树为:");
//        printTree(root);
        return root;
    }

    /**
     * @return 返回节点数目为16范围为1~100的树
     */
    public static Node getRandTree() {
        int[] arrays = ArrayUtil.randArrays(16, 100);
        Node root = arrayToRandTree(arrays);
        System.out.println("生成的树为:");
        printTree(root);
        return root;
    }


    // 计算树的最大深度
    public static int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    // 按正三角格式打印树
    public static void printTree(Node root) {
        int depth = maxDepth(root);
        if (depth == 0) {
            return;
        }
        int width = (int) Math.pow(2, depth) - 1;

        List<List<String>> result = new ArrayList<>();
        for (int i = 0; i < 2 * depth - 1; i++) {
            List<String> row = new ArrayList<>();
            for (int j = 0; j < width; j++) {
                row.add(" ");
            }
            result.add(row);
        }

        Queue<Node> nodes = new LinkedList<>();
        Queue<int[]> positions = new LinkedList<>();
        nodes.offer(root);
        positions.offer(new int[]{0, width / 2});

        while (!nodes.isEmpty()) {
            Node node = nodes.poll();
            int[] pos = positions.poll();
            int level = pos[0];
            int index = pos[1];

            if (index < 0 || index >= width || 2 * level >= 2 * depth - 1) {
                continue;
            }

            String nodeValue = node != null ? String.valueOf(node.data) : "N";
            int valueLength = nodeValue.length();
            int startIndex = index - valueLength / 2;
            for (int i = 0; i < valueLength; i++) {
                if (startIndex + i >= 0 && startIndex + i < width) {
                    result.get(2 * level).set(startIndex + i, String.valueOf(nodeValue.charAt(i)));
                }
            }

            if (node != null) {
                nodes.offer(node.left);
                int leftIndex = index - (int) Math.pow(2, depth - level - 2);
                if (2 * level + 1 < 2 * depth - 1 && leftIndex >= 0 && leftIndex < width) {
                    // 找到左子节点值的中心位置
                    String leftValue = node.left != null ? String.valueOf(node.left.data) : "N";
                    int leftValueLength = leftValue.length();
                    int leftCenter = leftIndex - leftValueLength / 2;
                    result.get(2 * level + 1).set(leftCenter + leftValueLength - 1, "/");
                }
                positions.offer(new int[]{level + 1, leftIndex});

                nodes.offer(node.right);
                int rightIndex = index + (int) Math.pow(2, depth - level - 2);
                if (2 * level + 1 < 2 * depth - 1 && rightIndex >= 0 && rightIndex < width) {
                    // 找到右子节点值的中心位置
                    String rightValue = node.right != null ? String.valueOf(node.right.data) : "N";
                    int rightValueLength = rightValue.length();
                    int rightCenter = rightIndex - rightValueLength / 2;
                    result.get(2 * level + 1).set(rightCenter, "\\");
                }
                positions.offer(new int[]{level + 1, rightIndex});
            }
        }

        // 打印结果
        for (List<String> row : result) {
            StringBuilder sb = new StringBuilder();
            for (String val : row) {
                sb.append(val);
            }
            System.out.println(sb.toString());
        }
    }

    /**
     * @param array 要转的数组
     * @return 返回将数组转成树
     */
    private static Node arrayToRandTree(int[] array) {
        Node root = new Node(array[0]);
        for (int i = 1; i < array.length; i++) {
            randInsertNode(root, array[i]);
        }
        return root;
    }

    /**
     * @param root 根
     * @param data 随机插入一个节点
     * @return 返回插入好了的根
     */
    private static void randInsertNode(Node root, int data) {
        if (root == null) {
            return;
        }
        Node newNode = new Node(data);
        while (true) {
            int rand = (int) (Math.random() * 2);
            if (rand == 1) { // 1 向根的左边插入
                if (root.left != null) {
                    root = root.left;
                } else {
                    root.left = newNode;
                    break;
                }
            } else {
                if (root.right != null) {
                    root = root.right;
                } else {
                    root.right = newNode;
                    break;
                }
            }
        }
    }
}
